package merisis.util;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;

import org.apache.solr.util.OpenBitSet;

public class BitUtil {

	/**
	 * list and format a string for the object of OpenBitSet.
	 */
	public static void format(StringBuilder sb, OpenBitSet bs, String sep) {

		if (bs == null) {
			sb.append("null");
			return;
		}

		long i = bs.nextSetBit(0);
		if (i >= 0) {
			sb.append(i);
			i = bs.nextSetBit(i + 1);
			while (i >= 0) {
				sb.append(sep);
				sb.append(i);
				i = bs.nextSetBit(i + 1);
			}
		}
	}

	public static void format(StringBuilder sb, long[] bs, String sep) {

		if (bs == null || bs.length == 0)
			return;

		sb.append(bs[0]);
		for (int i = 1; i < bs.length; i++) {
			sb.append(sep);
			sb.append(bs[i]);
		}
	}

	public static String toString(long[] array) {

		StringBuilder sb = new StringBuilder();
		sb.append("{");
		if (array != null) {
			format(sb, array, ",");
		}
		sb.append("}");

		return sb.toString();
	}

	public static String toString(long[][] array) {

		StringBuilder sb = new StringBuilder();
		sb.append("{");
		if (array != null) {
			for (long[] ay : array) {
				sb.append("{");
				format(sb, ay, ",");
				sb.append("}");
			}
		}
		sb.append("}");

		return sb.toString();
	}

	public static String toString(OpenBitSet bs) {
		StringBuilder sb = new StringBuilder();
		sb.append("{");
		if (bs != null) {
			format(sb, bs, ",");
		}
		sb.append("}");
		return sb.toString();
	}

	public static String toStringOfBitSetCollection(Collection<OpenBitSet> c) {

		StringBuilder sb = new StringBuilder();
		sb.append('{');

		while (true) {

			if (c == null)
				break;

			Iterator<OpenBitSet> itr = c.iterator();
			if (itr.hasNext()) {
				sb.append('{');
				BitUtil.format(sb, itr.next(), ",");
				sb.append('}');
			}

			while (itr.hasNext()) {
				sb.append(',');
				sb.append('{');
				BitUtil.format(sb, itr.next(), ",");
				sb.append('}');
			}

			break;
		}
		sb.append('}');

		return sb.toString();
	}

	public static OpenBitSet bitsetOrArray(OpenBitSet bs, long[] array) {

		for (int i = 0; i < array.length; i++) {
			bs.set(array[i]);
		}

		return bs;
	}

	public static BitSet toBitSet(long[] array) {

		BitSet bs = new OpenBitSetImpl();
		for (int i = 0; i < array.length; i++) {
			bs.set(array[i]);
		}

		return bs;
	}

	public static OpenBitSet bitsetClearArray(OpenBitSet bs, long[] array) {

		for (int i = 0; i < array.length; i++) {
			bs.clear(array[i]);
		}

		return bs;
	}

	public static long[] toArray(OpenBitSet s) {

		if (s == null)
			return null;

		long[] array = new long[(int) s.cardinality()];
		int k = 0;
		for (long i = s.nextSetBit(0); i >= 0; i = s.nextSetBit(i + 1)) {

			array[k] = i;
			k++;
		}

		return array;
	}

	private final static byte[] countOneOfByte = { 0, 1, 1, 2, 1, 2, 2, 3, 1,
			2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4,
			5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3,
			4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
			4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2,
			3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5,
			6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3,
			4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3,
			4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
			5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
			6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4,
			5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
			7, 6, 7, 7, 8 };

	public static long countOne(long x) {

		int count = 0;

		count += countOneOfByte[(int) (x & 0xff)];

		while (x != 0) {
			x >>>= 8;
			count += countOneOfByte[(int) (x & 0xff)];
		}
		return count;
	}

	/** table of number of trailing zeros in a byte */
	public static final byte[] ntzTable = { 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
			2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0,
			1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
			3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
			1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0,
			2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,
			1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0,
			1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
			2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0,
			1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0,
			3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
			1, 0 };

	/** Returns number of trailing zeros in the 64 bit long value. */
	public static int ntz(long val) {
		// A full binary search to determine the low byte was slower than
		// a linear search for nextSetBit(). This is most likely because
		// the implementation of nextSetBit() shifts bits to the right,
		// increasing
		// the probability that the first non-zero byte is in the rhs.
		//
		// This implementation does a single binary search at the top level only
		// so that all other bit shifting can be done on ints instead of longs
		// to
		// remain friendly to 32 bit architectures. In addition, the case of a
		// non-zero first byte is checked for first because it is the most
		// common
		// in dense bit arrays.

		int lower = (int) val;
		int lowByte = lower & 0xff;
		if (lowByte != 0)
			return ntzTable[lowByte];

		if (lower != 0) {
			lowByte = (lower >>> 8) & 0xff;
			if (lowByte != 0)
				return ntzTable[lowByte] + 8;
			lowByte = (lower >>> 16) & 0xff;
			if (lowByte != 0)
				return ntzTable[lowByte] + 16;
			// no need to mask off low byte for the last byte in the 32 bit word
			// no need to check for zero on the last byte either.
			return ntzTable[lower >>> 24] + 24;
		} else {
			// grab upper 32 bits
			int upper = (int) (val >> 32);
			lowByte = upper & 0xff;
			if (lowByte != 0)
				return ntzTable[lowByte] + 32;
			lowByte = (upper >>> 8) & 0xff;
			if (lowByte != 0)
				return ntzTable[lowByte] + 40;
			lowByte = (upper >>> 16) & 0xff;
			if (lowByte != 0)
				return ntzTable[lowByte] + 48;
			// no need to mask off low byte for the last byte in the 32 bit word
			// no need to check for zero on the last byte either.
			return ntzTable[upper >>> 24] + 56;
		}
	}
	
	public static long longsqrt(long x) {

		long squaredbit, remainder, root;

		if (x < 1)
			return 0;

		squaredbit = ((-1L >>> 1) & ~(-1L >>> 2));

		remainder = x >>> 2;
		squaredbit = 1;
		while (remainder > 0) {
			remainder >>>= 2;
			squaredbit <<= 2;
		}

		remainder = x;
		root = 0;
		while (squaredbit > 0) {
			if (remainder >= (squaredbit | root)) {
				remainder -= (squaredbit | root);
				root >>>= 1;
				root |= squaredbit;
			} else {
				root >>>= 1;
			}
			squaredbit >>>= 2;
		}

		return root;
	}


	/**
	 * Number of leading zeros.
	 */
	public static int nlz(long x) {
		// 'Hackers Delight', Copyright 2002, H. S. Warren.
		// Number of leading zeros, binary search, counting down
		
		long y;
		int n;

		n = 64;

		y = x >> 32;
		if (y != 0) {
			n = n - 32;
			x = y;
		}

		y = x >> 16;
		if (y != 0) {
			n = n - 16;
			x = y;
		}

		y = x >> 8;
		if (y != 0) {
			n = n - 8;
			x = y;
		}
		
		y = x >> 4;
		if (y != 0) {
			n = n - 4;
			x = y;
		}
		
		y = x >> 2;
		if (y != 0) {
			n = n - 2;
			x = y;
		}
		
		y = x >> 1;
		if (y != 0)
			return n - 2;
		
		return n - (int)x;
	}
}